#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <cstring>

typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    int size;
    int capacity;
}Heap;

// typedef int DataType;
// struct Node
// {
//     struct Node* firstchild;
//     struct Node* nextBrother;
//     DataType data;
// };

void Swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

//建立小堆
void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while(child < n)
    {
        if(child + 1 < n && a[child+1] < a[child])
        {
            //右孩子小于左孩子;
            child++;
        }

        if(a[child] < a[parent])
        {
            //交换父节点和子结点.
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            //以及是堆了.
            break;
        }
    }
}

//建立大堆
// void AdjustDown(int* a, int n, int parent)
// {
//     int child = parent * 2 + 1;
//     while(child < n)
//     {
//         if(child + 1 < n && a[child+1] > a[child])
//         {
//             //右孩子小于左孩子;
//             child++;
//         }

//         if(a[child] > a[parent])
//         {
//             //交换父节点和子结点.
//             Swap(&a[parent], &a[child]);
//             parent = child;
//             child = parent * 2 + 1;
//         }
//         else
//         {
//             //以及是堆了.
//             break;
//         }
//     }
// }

// int main()
// {
//     for(int i = (n-1-1) / 2; i >= 0; i--)
//     {
//         AdjustDown(p->a, p->size, i);
//     }
//     return 0;
// }

void AdjustUp(HPDataType* a, int child)
{
    int parent = (child-1) / 2;
    while(child > 0)
    {
        if(a[child] < a[parent])
        {
            Swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);

    //开辟n个空间;
    HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType )* n);
    if(tmp == nullptr)
    {
        printf("malloc fail!\n");
        exit(-1);
    }
    hp->a = tmp;
    //将a数据拷贝到hp->a里面;
    memcpy(hp->a, a, sizeof(HPDataType)*n);
    hp->size = n;
    hp->capacity = n;

    for(int i = (hp->size-1-1) / 2; i >= 0; i--)
    {
        //建立小堆;向下调整建堆.
        AdjustDown(hp->a, hp->size, i);
    }
}

void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->a);
    hp->a = nullptr;
    hp->size = hp->capacity = 0;
}

int depth(int n)
{
    assert(n >= 0);

    if(n > 0)
    {
        int m = 2;
        int height = 1;
        while(m < n + 1)
        {
            m *= 2;
            height++;
        }
        return height;
    }
    else
    {
        return 0;
    }
}

// void HeapPrint(Heap* hp)
// {
//     assert(hp);

//     for(int i = 0; i < hp->size; i++)
//     {
//         printf("%d ", hp->a[i]);
//     }
//     printf("\n");

//     int h = depth(hp->size);
//     int N = (int)pow(2, h) - 1;
//     int space  
// }


void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if(hp->size == hp->capacity)
    {
        HPDataType* tmp = (HPDataType*)realloc(hp->a, 2 * hp->capacity * sizeof(HPDataType));
        if(tmp == nullptr)
        {
            printf("realloc fail!\n");
            exit(-1);
        }
        hp->a = tmp;
        hp->capacity *= 2;
    }
    hp->a[hp->size] = x;
    hp->size++;

    //插入数据后需要保持堆结构采用向上调整法:
    AdjustUp(hp->a, hp->size-1);
}

bool HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->size == 0;
}

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));

    //交换堆顶和堆底元素
    Swap(&hp->a[0], &hp->a[hp->size-1]);
    hp->size--;

    AdjustDown(hp->a, hp->size, 0);
}

HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    return hp->a[0];
}

int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->size;
}


// int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
// {
//     *returnSize = k;
//     //建立小堆.
//     for(int i = (arrSize-1-1) / 2; i >= 0; i--)
//     {
//         AdjustDown(arr, arrSize, i);
//     }

//     //排降序;
//     int end = arrSize - 1;
//     while(end > 0)
//     {
//         Swap(&arr[0], &arr[end]);
//         AdjustDown(arr, end, 0);
//         end--;
//     }

//     int* retArr = (int*)malloc(sizeof(int) * k);
//     for(int i = 0; i < k; i++)
//     {
//         retArr[i] = arr[i];
//     }
//     return retArr;
// }


// int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
// {
//     *returnSize = k;
//     for(int i = (arrSize-1-1) / 2; i >= 0; i--)
//     {
//         AdjustDown(arr, arrSize, i);
//     }

//     //将最大k个数保持到数组;
//     int* retArr = (int*)malloc(sizeof(int) * k);
//     int end = arrSize - 1;
//     for(int i = 0; i < k; i++)
//     {
//         retArr[i] = arr[0];
//         Swap(&arr[0], &arr[end]);
//         AdjustDown(arr, end, 0);
//         end--;
//     }
//     return retArr;
// }

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
    *returnSize = k;
    if(k == 0)
        return nullptr;

    int* retArr = (int*)malloc(sizeof(int) * k);
    for(int i = 0; i < k; i++)
    {
        retArr[i] = arr[i];
    }

    //前k个数建小堆;
    for(int i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(retArr, k, i);
    }

    //将后n-k个数据每一个和retArr[0]进行比较, 
    //然后每次在k个里面选出最小和n-k个数据进行比较交换调整.
    for(int i = k; i < arrSize; i++)
    {
        if(arr[i] > retArr[0])
        {
            retArr[0] = arr[i];
        }
        AdjustDown(retArr, k, 0);
    }
    return retArr;
}


typedef char BTDataType;

typedef struct BTNode
{
    BTDataType data;
    struct  BTNode* left;
    struct  BTNode* right;
}BTNode;


void BinaryPrevOrder(BTNode* root)
{
    //前序遍历: 根->左子树->右子树
    if(root == nullptr)
        return;
    printf("%c ", root->data);
    BinaryPrevOrder(root->left);
    BinaryPrevOrder(root->right);
}

void BinaryInOrder(BTNode* root)
{
    //中序遍历: 左子树->根->右子树;
    if(root == nullptr)
        return;
    
    BinaryInOrder(root->left);
     printf("%c ", root->data);
    BinaryInOrder(root->right);
}

void BinaryPostOrder(BTNode* root)
{
    //后序遍历: 左子树->右子树->根;
   if(root == nullptr)
        return;
    
    BinaryPostOrder(root->left);
    BinaryPostOrder(root->left);
    printf("%c ", root->data);
}

#include "Queue.cc"

// void BinaryLevelOrder(BTNode* root)
// {
//     Queue q;
//     QueueInit(&q);
//     if(root != nullptr)
//         QueuePush(&q, root);
    
//     while(!QueueEmpty(&q))
//     {
//         BTNode* front = QueueFront(&q);
//         QueuePop(&q);
//         printf("%c ", front->data);
//         if(front->left)
//         {
//             QueuePush(&q, front->left);
//         }
//         if(front->right)
//         {
//             QueuePush(&q, front->right);
//         }
//     }
//     QueueDestroy(&q);
// }

int BinaryTreeSize(BTNode* root)
{
    return root == nullptr ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}


int BinaryTreeLeafSize(BTNode* root)
{
    if(root == nullptr)
        return 0;
    
    if(root->left == nullptr && root->right == nullptr)
    {
        return 1;
    }

    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if(k < 1 || root == nullptr) 
        return 0;
    
    if(k == 1)
        return 1;
    
    return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right, k-1); 
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if(root == nullptr)
        return nullptr;
    
    if(root->data == x)
        return root;
    
    BTNode* left = BinaryTreeFind(root->left, x);
    if(left)
        return left;
    BTNode* right = BinaryTreeFind(root->right, x);
    if(right)
        return right;
    return nullptr;
}

int Max(int a, int b)
{
    return a > b ? a : b;
}

int BinaryTreeMaxDepth(BTNode* root)
{
    if(root == nullptr)
        return 0;
    
    return Max(BinaryTreeMaxDepth(root->left), BinaryTreeMaxDepth(root->right));
}